package org.liaohailong.helloworld.example;

import androidx.annotation.NonNull;

import java.util.Arrays;

/**
 * Author: liaohailong
 * Date: 2021/8/9
 * Time: 20:56
 * Description:
 **/
public class SortTest {

    //        给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行分类，使得相同颜色的元素相邻，并按照白色、红色、蓝色顺序排列。
//        此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//        注意:
//        不能使用代码库中的排序函数来解决这道题
//        [2,0,2,1,1,0]
//        [1,1,0,0,2,2]
    public static void main(String[] args) {
        // 数据源
        int[] arr = {2, 0, 2, 1, 1, 0};
        // 重新定义优先级
        final int[] priority = new int[3];
        priority[0] = 1;
        priority[1] = 0;
        priority[2] = 2;
        // 快排
        quickSort(arr, new Comparator() {
            @Override
            public int compare(int i1, int i2) {
                int result;
                if (priority[i1] > priority[i2])
                    result = -1;
                else if (priority[i1] < priority[i2])
                    result = 1;
                else result = 0;
                return result;
            }
        });


        System.out.print(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, @NonNull Comparator comparator) {
        _quickSort(arr, 0, arr.length - 1, comparator);
    }

    private static void _quickSort(int[] arr, int start, int end, @NonNull Comparator comparator) {
        if (start < end){
            int mid = _partition(arr, start, end, comparator);
            _quickSort(arr, start, mid - 1, comparator);
            _quickSort(arr, mid + 1, end, comparator);
        }
    }

    private static int _partition(int[] arr, int start, int end, @NonNull Comparator comparator) {
        int temp = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while (comparator.compare(arr[j], temp) <= 0 && i < j) j--;
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (comparator.compare(arr[i], temp) >= 0 && i < j) i++;
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = temp;
        return i;
    }

    private interface Comparator {
        int compare(int i1, int i2);
    }

}
